package ACWing.SearchAndGraphTheory.最短路;
//851. spfa求最短路

import java.util.*;

/**
 * @author :chenjie
 * @date :Created 2022/12/31 20:19
 */
public class SpFa {

    static int n , m , N = 1000010;
    static int[] dist = new int[N];//距离数组
    static boolean[] st = new boolean[N];//标记数组
    static int[] h = new int[N], ne = new int[N], e = new int[N], w = new int[N];//邻接表
    static int idx ;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        Arrays.fill(h,-1);
        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            add(a,b,c);
        }
        int x=spfa();
        if(x==0x3f3f3f3f){
            System.out.println("impossible");
        }else{
            System.out.println(x);
        }

    }
    static int spfa(){
        Arrays.fill(dist,0x3f3f3f3f);
        Queue<Integer>queue=new ArrayDeque<>();
        queue.add(1);
        st[1]=true;
        dist[1]=0;
        while (!queue.isEmpty()){
            int remove = queue.remove();
            st[remove]=false;
            for (int i = h[remove]; i !=-1; i=ne[i]) {
                int j=e[i];
                if(dist[j]>dist[remove]+w[i]){
                    dist[j]=dist[remove]+w[i];
                    if(!st[j]){
                        queue.add(j);
                        st[j]=true;
                    }
                }
            }
        }
       return dist[n];
    }
    public static void add(int a,int b,int c){
        e[idx]=b;
        ne[idx]=h[a];
        w[idx]=c;//存储到b的权值
        h[a]=idx++;
    }
}
